package week_06;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            List<List<Integer>> tmpAns = threeSum(nums, i + 1, target-nums[i], nums[i]);
            ans.addAll(tmpAns);
        }
        return ans;

    }

    public List<List<Integer>> threeSum(int[] nums, int start, int target, int s1) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            List<List<Integer>> tmpAns = twoSum(nums, i + 1, target - nums[i], s1, nums[i]);
            ans.addAll(tmpAns);
        }
        return ans;
    }

    public List<List<Integer>> twoSum(int[] nums, int start, int target, int s1, int s2) {
        List<List<Integer>> ans = new ArrayList<>();
        int j = nums.length - 1;
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            while (i < j && nums[i] + nums[j] > target) j--;
            if (i < j && nums[i] + nums[j] == target) {
                int i1 = nums[i];
                int i2 = nums[j];
                ans.add(new ArrayList<Integer>() {{
                    add(s1);
                    add(s2);
                    add(i1);
                    add(i2);
                }});
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        FourSum test = new FourSum();
        int[] arr = new int[]{2,2,2,2,2};
        List<List<Integer>> ans = test.fourSum(arr, 8);
        for (List<Integer> item : ans) {
            for (int val : item) {
                System.out.print(val + ",");
            }
            System.out.println();
        }
    }
}
